// BFSTraversal.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include <iostream>
#include <stack>
#include <queue>
#include <deque>
using namespace std;

struct TreeNode
{
    int value;
    TreeNode *left, *right;
};

// Given a binary tree, print out the tree nodes level by level in zig zag level order, i.e. from left to right, then right to left for the next level and alternate between.
// Output a newline after the end of each level.
//
// Algorithm: Iteration
//            Using 2 stacks, BFS traverse the tree.
//            When pushing child nodes into stack 1, left child first
//            when pushing child nodes into stack 2, right child first
//            when a stack is empty, output a newline
// Analysis:
//   Time Complexity: O(n)
void BFS_ZigZag(TreeNode *root)
{
    if(!root) return;
    stack<TreeNode *> s1,s2;
    s1.push(root);
    int indicator=1;

    while(!s1.empty()||!s2.empty())
    {
        if(indicator==1)
        {
            if(s1.empty())
            {
                cout<<endl;
                indicator=2;
            }
            else
            {
                TreeNode *p=s1.top();
                s1.pop();
                cout<<p->value<<" ";
                if(p->right)
                {
                    s2.push(p->right);
                }
                if(p->left)
                {
                    s2.push(p->left);
                }
            }
        }
        else if(indicator==2)
        {
            if(s2.empty())
            {
                cout<<endl;
                indicator=1;
            }
            else
            {
                TreeNode *p=s2.top();
                s2.pop();
                cout<<p->value<<" ";
                if(p->left)
                {
                    s1.push(p->left);
                }
                if(p->right)
                {
                    s1.push(p->right);
                }
            }
        }
        else
            throw;
    }
}

// MSFT:
// Given a binary tree, print out the tree nodes in left-to-right and level by level
// Output a newline after the end of each level.

// Algorithm: Iteration
//            Using 2 queues, BFS traverse the tree.
//            When pushing child nodes into a queue, left child first
//            when a queue is empty, output a newline
// Analysis:
//   Time Complexity: O(n)
void BFS_Left2Right_2Q(TreeNode *root)
{
    if(!root) return;
    queue<TreeNode *> q1,q2;
    q1.push(root);
    int indicator=1;

    while(!q1.empty()||!q2.empty())
    {
        if(indicator==1)
        {
            if(q1.empty())
            {
                cout<<endl;
                indicator=2;
            }
            else
            {
                TreeNode *p=q1.front();
                q1.pop();
                cout<<p->value<<" ";
                if(p->left) q2.push(p->left);
                if(p->right) q2.push(p->right);
            }
        }
        else if(indicator==2)
        {
            if(q2.empty())
            {
                cout<<endl;
                indicator=1;
            }
            else
            {
                TreeNode *p=q2.front();
                q2.pop();
                cout<<p->value<<" ";
                if(p->left) q1.push(p->left);
                if(p->right) q1.push(p->right);
            }
        }
        else
            throw;
    }
}

// Same question as above.
//
// Algorithm:
//    Using 1 queue, BFS traverse the tree.
//      1. when popping a node off the queue, currentLevelNodes - 1
//      2. when pushing a node to the queue, nextLevelNodes + 1
//      3. when currentLevelNodes == 0, output a newline and swap currentLevelNodes and nextLevelNodes
// Analysis:
//   Time Complexity: O(n)
void BFS_Left2Right_1Q(TreeNode *root)
{
    if(!root) return;
    queue<TreeNode *> q;
    int currentLevelNodes=0,nextLevelNodes=0;
    q.push(root);
    ++currentLevelNodes;

    while(!q.empty())
    {
        TreeNode *p=q.front();
        q.pop();
        --currentLevelNodes;
        cout<<p->value<<" ";

        if(p->left)
        {
            q.push(p->left);
            ++nextLevelNodes;
        }

        if(p->right)
        {
            q.push(p->right);
            ++nextLevelNodes;
        }

        if(!currentLevelNodes)
        {
            cout<<endl;
            currentLevelNodes=nextLevelNodes;
            nextLevelNodes=0;
        }
    }
}

// Same question as above.
//
// Algorithm: DFS pre-order traverse the tree. Decrement level by one as advance to the next level.
//            When level equals 1, output the node value.
// Analysis:
//   Time Complexity: O(n^2), as print each level requires O(n)

int Height(TreeNode *root)
{
    if(root) return 0;

    int h1=Height(root->left);
    int h2=Height(root->right);
    return (h1>h2 ? h1:h2)+1;
}

void DFS_Left2Right(TreeNode *node, int level)
{
    if(!node) return;

    if(level==1)
    {
        cout<<node->value<<" ";
    }
    else
    {
        DFS_Left2Right(node->left,level-1);
        DFS_Left2Right(node->right,level-1);
    }
}

void DFS_Left2Right(TreeNode *root)
{
    if(!root) return;

    for(int level=1;level<=Height(root);level++)
    {
        DFS_Left2Right(root,level);
        cout<<endl;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    return getchar();
}